<h2>Problem 159</h2>
<div style="color:#666;font-size:80%;">30 June 2007</div><br />
<div class="problem_content">
<p>A composite number can be factored many different ways.  
For instance, not including multiplication by one, 24 can be factored in 7 distinct ways:</p>
<div style="margin-left:50px;">
24 = 2x2x2x3<br />
24 = 2x3x4<br />
24 = 2x2x6<br />
24 = 4x6<br />
24 = 3x8<br />
24 = 2x12<br />
24 = 24
</div>
<p>Recall that the digital root of a number, in base 10, is found by adding together the digits of that number, 
and repeating that process until a number is arrived at that is less than 10.  
Thus the digital root of 467 is 8.</p>
<p>We shall call a Digital Root Sum (DRS) the sum of the digital roots of the individual factors of our number.<br />
 The chart below demonstrates all of the DRS values for 24.</p>
<table align="center" border="1" cellpadding="2" cellspacing="0">
<tr><th>Factorisation</th><th>Digital Root Sum</th></tr>
<tr><td><div style="margin-left:20px;">2x2x2x3</div></td>
<td><div style="text-align:center;">9</div></td></tr>
<tr><td><div style="margin-left:20px;">2x3x4</div></td>
<td><div style="text-align:center;">9</div></td></tr>
<tr><td><div style="margin-left:20px;">2x2x6</div></td>
<td><div style="text-align:center;">10</div></td></tr>
<tr><td><div style="margin-left:20px;">4x6</div></td>
<td><div style="text-align:center;">10</div></td></tr>
<tr><td><div style="margin-left:20px;">3x8</div></td>
<td><div style="text-align:center;">11</div></td></tr>
<tr><td><div style="margin-left:20px;">2x12</div></td>
<td><div style="text-align:center;">5</div></td></tr>
<tr><td><div style="margin-left:20px;">24</div></td>
<td><div style="text-align:center;">6</div></td></tr>
</table>
<p>The maximum Digital Root Sum  of 24 is 11.<br />
The function mdrs(<var>n</var>) gives the maximum Digital Root Sum of <var>n</var>. So  mdrs(24)=11.<br />
Find <img src='images/symbol_sum.gif' width='11' height='14' alt='&sum;' border='0' style='vertical-align:middle;' />mdrs(<var>n</var>) for 1 <img src='images/symbol_lt.gif' width='10' height='10' alt='&lt;' border='0' style='vertical-align:middle;' /> <var>n</var> <img src='images/symbol_lt.gif' width='10' height='10' alt='&lt;' border='0' style='vertical-align:middle;' /> 1,000,000.</p>
</div><br />
